﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml;

namespace pptrbt
{
    class pptrbt
    {
        pptrbnode root;
        pptrbnode sentinelNode;


                
        int count;
        pptgenerator pptg;
        
        string InputFName;
        String OutputFName;
        string TemplateFName;

        int noderadius;
        int margin;
        int deletecase3rlalternate;
     

        public pptrbt(string pfn1, string pfn2, string pfn3)
        {
           
             // set up the sentinel node. the sentinel node is the key to a successfull
            // implementation and for understanding the red-black tree properties.
            sentinelNode = new pptrbnode();
            sentinelNode.left = null;
            sentinelNode.right = null;
            sentinelNode.parent = null;
            sentinelNode.data = -1000; // a special value help debug
            sentinelNode.Color = pptrbnode.BLACK;
            root = sentinelNode;
            //root = null;
            count = 0;

            InputFName = pfn2;
            OutputFName = pfn3;
            TemplateFName = pfn1;
            pptg = new pptgenerator(TemplateFName);
            margin = 40;
            noderadius = 10;

            deletecase3rlalternate = 0;

        }

        


        public void process()
        {

            try
            {

                XmlDocument xmldoc = new XmlDocument();
                xmldoc.Load(InputFName);

                XmlNodeList xlist = xmldoc.SelectNodes("/bst/*");

                //PARSE INFO
                foreach (XmlNode xn in xlist)
                {
                    
                    dispatch(xn);

                    
                    

                }

                pptg.saveppt(OutputFName);
            }
            catch (Exception ex)
            {
                //MessageBox.Show("Error: " + ex.Message);
                Console.WriteLine("Error: " + ex.Message);
            }
        
        }

        private void drawtree(int start, int width, int height, int margin, int r)
        {
            int treeheight = root.getheight();
        
            int verticalinterval = (height - 2 * margin) / treeheight;
            
            root.calculatecoordinates(start, width, margin, verticalinterval, r);

          
            root.drawnode(start + width / 2, margin, pptg, pptrbnode.BLACK);

            
        }

        

        private void dispatch(XmlNode xn)
        {
            
            if (xn.Name == "add")
            { 
                insert(Convert.ToInt16(xn.InnerText.ToString())); 
            }
            else if (xn.Name == "delete")
            { 
                delete(Convert.ToInt16(xn.InnerText.ToString())); 
            }
             
           


          /*

           else if (xn.Name == "dft")
           {
               //if (op == "pre")
               //   Print(1);
               //else if (op == "in")
               // Print(2);
               // else
               // Print(3);

           }
           else if (xn.Name == "bft")
           { tool.demo(master.getHeight()); }

           else if (xn.Name == "FindHeight")
           { }//height(); }

           else if (xn.Name == "GetSize")
           { }//size(); }
           else if (xn.Name == "Fpred")
           { fpred(op); }
           else if (xn.Name == "Fsuc")
           { fsucc(op); }
           * */
        }

     

        public  pptrbnode Find(int pdata)
        {
            return SubtreeFind(root, pdata);
        }


        /* Given:  Current  A pointer to a node in the implicit binary search tree.
           Item     A data item to look for.
        Task:   To search for Item in the subtree rooted at the node Current
           points to.
        Return: A pointer to the node where Item was found or a null pointer
           if it was not found.
        */

        private pptrbnode SubtreeFind(pptrbnode Current, int pdata)
        {
            if (Current == null)
                return null;
            else if (pdata == Current.data)
                return Current;
            else if (pdata < Current.data)
                return SubtreeFind(Current.left, pdata);
            else
                return SubtreeFind(Current.right, pdata);
        }

        
         public  pptrbnode delete(int pdata)
        {
            pptrbnode tbr;
             pptrbnode tmp = Find(pdata);
        
            if (tmp == null)
            {
                // the data is not existing.
                tbr = null;
            }
            
            else if ((tmp.left == null) && (tmp.right == null))
            {
                //it is a leaf
                if (pdata>tmp.parent.data)
                    tmp.parent.right = null;
                else
                    tmp.parent.left = null;

                //how to delete tmp;
                tbr = tmp.parent;
            }
                //there must be one not null
            else if (tmp.left==null )
            {
                //it must have right subtree
                if (pdata > tmp.parent.data)
                    tmp.parent.right = tmp.right;
                else
                    tmp.parent.left = tmp.right;
                tbr = tmp.parent;
            }
            else if (tmp.right == null)
            { 
                //it has left subtree
                
                if (pdata > tmp.parent.data)
                    tmp.parent.right = tmp.left;
                else
                    tmp.parent.left = tmp.left;
                tbr = tmp.parent;
            }
            else
            {
                //it has two subtrees.
                //copy
                pptrbnode tbd;
                if (deletecase3rlalternate == 0)
                {
                    tbd = findpredecessor(pdata);
                    deletecase3rlalternate = 1;
                }
                else
                {
                    tbd = findsuccessor(pdata);
                    deletecase3rlalternate = 0;
                }

                 //copy
                tmp.data= tbd.data;
                tbr=tbd.parent;
                
                delete(tbd);
                count--;

                
            }

           return tbr;
        }

        void delete(pptrbnode tmp)
        {

            if ((tmp.left == null) && (tmp.right == null))
            {
                //it is a leaf
                if (tmp.data > tmp.parent.data)
                    tmp.parent.right = null;
                else
                    tmp.parent.left = null;

                //how to delete tmp;
            }
            //there must be one not null
            else if (tmp.left == null)
            {
                //it must have right subtree
                if (tmp.data > tmp.parent.data)
                    tmp.parent.right = tmp.right;
                else
                    tmp.parent.left = tmp.right;

            }
            else if (tmp.right == null)
            {
                //it has left subtree

                if (tmp.data > tmp.parent.data)
                    tmp.parent.right = tmp.left;
                else
                    tmp.parent.left = tmp.left;

            }
        }

        // a key's predecessor is the key in the rightmost node in the left subtree
        
        pptrbnode findpredecessor(int pdata)
        {
            pptrbnode tmp = Find(pdata);
            if (tmp == null)
                return null;

            pptrbnode c = tmp.left;

            while (c.right!= null)
            {
                c = c.right;
            }

            return c;

            
        
        }
        
     

        //analogically, its immediate successor is the key in the leftmost node in the right subtree
        pptrbnode findsuccessor(int pdata)
        {

            pptrbnode tmp = Find(pdata);
            if (tmp == null)
                return null;

            pptrbnode c = tmp.right;

            while (c.left != null)
            {
                c = c.left;
            }

            return c;

        }
        
         
   /*
        public override void drawtree(int start, int width, int height, int margin, int r)
        {
            int treeheight = root.getheight();

            int verticalinterval = (height - 2 * margin) / treeheight;

            root.calculatecoordinates(start, width, margin, verticalinterval, r);


            root.drawnode(start + width / 2, margin, pptg);


        }
    */ 


        private void nextslide()
        {
            pptg.newslide();

            drawtree(margin, pptg.w, pptg.h, margin, noderadius);
        }

        // notice that insert of bst is virtual, so when process calls for insert, overridden avl insert will be called.
        public void insert(int pdata)
        {

            //Console.WriteLine("in Avl insert 1");


            //base.insert(pdata); // insert as normal bst node first

            pptrbnode Current, Parent;
            pptrbnode Tmp;

            if (Find(pdata) != null)
            {
                Console.WriteLine("Existed Already!");
                return;
            }

            // since pdata doesn't exist, we can insert
            Current = root;
            Parent = null;

            while (Current != sentinelNode)
            {

                Parent = Current;
                if (pdata < Current.data)
                    Current = Current.left;
                else
                    Current = Current.right;
            }

            Tmp = new pptrbnode(pdata);

            if (Parent == null)
                root = Tmp;
            else if (pdata < Parent.data)
                Parent.left = Tmp;
            else
                Parent.right = Tmp;

            Tmp.parent = Parent;
            Tmp.right = sentinelNode;
            Tmp.left = sentinelNode;

            nextslide();

            count++;

            //check balance of the 
            //Console.WriteLine("in redblack insert 2");

            RestoreAfterInsert(Tmp);           // restore red-black properities

           
        }
        //null here is really sentinelNode. Hidden by search
        private void RestoreAfterInsert(pptrbnode x)
        {
            // x and y are used as variable names for brevity, in a more formal
            // implementation, you should probably change the names

            pptrbnode y;

            // maintain red-black tree properties after adding x
            // if parent is black, adding a red one doesn't violate rbt, so, adjustment is delayed which is desired
            while (x != root && ((pptrbnode)(x.parent)).Color == pptrbnode.RED)
            {
                // Parent node is currrently .Colored red, and since the new node is always red based on our implementation, we need to adjust 
                if (x.parent == x.parent.parent.left)	// determine traversal path			
                {										// is it on the Left or Right subtree?
                    y = (pptrbnode)x.parent.parent.right;			// get uncle
                    if (y != null && y.Color == pptrbnode.RED)
                    {	// uncle is red; change x's Parent and uncle to black
                        ((pptrbnode)x.parent).Color = pptrbnode.BLACK;
                        y.Color = pptrbnode.BLACK;
                        //grandparent must have been black, because every red node that is not a leaf has only black children
                        // but after recolored uncle and parent generation, grandparent should be colored red, unifying the red one level up.
                        // grandparent must be red. Why? Every red node that is not a leaf has only black children ? This is illogical, unsound reasoning. 
                        //since on the path, uncle and parent layer has been recolored from red to black, 
                        //grandparent will be recolored to red to maintain the orginal number of reds in comparision with other root-initiated paths.
                        ((pptrbnode)x.parent.parent).Color = pptrbnode.RED;
                        x = (pptrbnode)x.parent.parent;	// continue loop with grandparent propogated bottom up
                    }
                    else
                    {
                        // uncle is black; determine if x is greater than Parent 
                        //two cases, the first iteration, it must be sentinel, but when red it squeezed up, this might be a value node. Is this right??
                        if (x == x.parent.right)
                        {	// yes, x is greater than Parent; rotate Left
                            // make x a Left child
                            x = (pptrbnode)(x.parent);
                            RotateLeft(x);
                            nextslide();
                        }
                        // no, x is less than Parent
                        ((pptrbnode)x.parent).Color = pptrbnode.BLACK;	// make Parent black
                        ((pptrbnode)x.parent.parent).Color = pptrbnode.RED;		// make grandparent black
                        RotateRight(x.parent.parent);					// rotate right
                        nextslide();
                    }
                }
                else
                {	// x's Parent is on the Right subtree
                    // this code is the same as above with "Left" and "Right" swapped
                    y = (pptrbnode)(x.parent.parent.left);
                    if (y != null && y.Color == pptrbnode.RED)
                    {
                        ((pptrbnode)x.parent).Color = pptrbnode.BLACK;
                        y.Color = pptrbnode.BLACK;
                        ((pptrbnode)x.parent.parent).Color = pptrbnode.RED;
                        x = (pptrbnode)x.parent.parent;
                    }
                    else
                    {
                        if (x == x.parent.left)
                        {
                            x = (pptrbnode)x.parent;
                            RotateRight(x);
                            nextslide();
                        }
                        ((pptrbnode)x.parent).Color = pptrbnode.BLACK;
                        ((pptrbnode)x.parent.parent).Color = pptrbnode.RED;
                        RotateLeft(x.parent.parent);
                        nextslide();
                    }
                }
            }
            root.Color = pptrbnode.BLACK;		// rbTree should always be black
        }

        ///<summary>
        /// RotateLeft
        /// Rebalance the tree by rotating the nodes to the left
        ///</summary>
        public void RotateLeft(pptrbnode x)
        {
            // pushing node x down and to the Left to balance the tree. x's Right child (y)
            // replaces x (since y > x), and y's Left child becomes x's Right child 
            // (since it's < y but > x).

            pptrbnode y = x.right;			// get x's Right node, this becomes y

            // set x's Right link
            x.right = y.left;					// y's Left child's becomes x's Right child

            // modify parents
            if ((pptrbnode)(y.left) != sentinelNode)
                y.left.parent = x;				// sets y's Left Parent to x

            if ((pptrbnode)y != sentinelNode)
                y.parent = x.parent;			// set y's Parent to x's Parent

            if (x.parent != null)
            {	// determine which side of it's Parent x was on
                if (x == x.parent.left)
                    x.parent.left = y;			// set Left Parent to y
                else
                    x.parent.right = y;			// set Right Parent to y
            }
            else
                root = (pptrbnode)y;						// at rbTree, set it to y

            // link x and y 
            y.left = x;							// put x on y's Left 
            if (x != sentinelNode)						// set y as x's Parent
                x.parent = y;
        }
        ///<summary>
        /// RotateRight
        /// Rebalance the tree by rotating the nodes to the right
        ///</summary>
        public void RotateRight(pptrbnode x)
        {
            // pushing node x down and to the Right to balance the tree. x's Left child (y)
            // replaces x (since x < y), and y's Right child becomes x's Left child 
            // (since it's < x but > y).

            pptrbnode y = x.left;			// get x's Left node, this becomes y

            // set x's Right link
            x.left = y.right;					// y's Right child becomes x's Left child

            // modify parents
            if ((pptrbnode)(y.right) != sentinelNode)
                y.right.parent = x;				// sets y's Right Parent to x

            if (y != sentinelNode)
                y.parent = x.parent;			// set y's Parent to x's Parent

            if (x.parent != null)				// null=rbTree, could also have used rbTree
            {	// determine which side of it's Parent x was on
                if (x == x.parent.right)
                    x.parent.right = y;			// set Right Parent to y
                else
                    x.parent.left = y;			// set Left Parent to y
            }
            else
                root = (pptrbnode)y;						// at rbTree, set it to y

            // link x and y 
            y.right = x;						// put x on y's Right
            if (x != sentinelNode)				// set y as x's Parent
                x.parent = y;
        }


        /*
       pptavlnode rotate(pptavlnode t)
        {
            int rh, lh;
            pptavlnode tmp, newt=null;

           //following wikipedia avl
            if (t.balance == -2)
            {
                // check right
                if (t.right.right == null)
                    rh = 0;
                else
                    rh = t.right.right.getheight();

                if (t.right.left == null)
                    lh = 0;
                else
                    lh = t.right.left.getheight();

                if (lh - rh == 1)
                { 
                    //right rotate of the right-left


                    tmp = (pptavlnode)t.right;

                    t.right.left.parent = t;
                    t.right = t.right.left;


                    if (tmp.left.right != null)
                        tmp.left.right.parent = tmp;

                    tmp.left = tmp.left.right;
                   

                    t.right.right = tmp;
                    tmp.parent = t.right;

                    pptg.newslide();
                    drawtree(margin, pptg.w, pptg.h, margin, noderadius);

                    // this won't involve the root at all.
                  
                }
                
                //now it must be -1, finally need to do left rotation anyway, this time on t
                //left rotation (regardless left rotation of the 
                //here root may be replaced.

                newt = (pptavlnode )t.right;
                t.right.parent = t.parent;
                if (t.parent != null)
                {
                    if (t.data > t.parent.data)
                        t.parent.right = t.right;
                    else
                        t.parent.left = t.right;

                }
                else
                    root = (pptavlnode)t.right; //tricky place, need to fix root as well.
                if (t.right.left != null)
                    t.right.left.parent = t;

                tmp = (pptavlnode)t.right.left; // save it temporarily
                t.right.left = t;
                t.parent = t.right;
                t.right = tmp;

                pptg.newslide();
                drawtree(margin, pptg.w, pptg.h, margin, noderadius);
            }

            else if (t.balance==2)
            {
               // check left 
                if (t.left.right == null)
                    rh = 0;
                else
                    rh = t.left.right.getheight();

                if (t.left.left == null)
                    lh = 0;
                else
                    lh = t.left.left.getheight();

                if (lh - rh == -1)
                {
                    //left rotate of the left-right
                    // no root involved
                    tmp = (pptavlnode)t.left;

                    t.left.right.parent = t;
                    t.left = t.left.right;

                    if (tmp.right.left != null)
                        tmp.right.left.parent = tmp;

                    tmp.right = tmp.right.left;
                                
                    
                    t.left.left = tmp;
                    tmp.parent = t.left;

                    pptg.newslide();
                    drawtree(margin, pptg.w, pptg.h, margin, noderadius);
                 
                }

                //now it must be 1, finally need to do left rotation anyway, this time on t
                //right rotation (regardless rotation of the 
                // it may involve root

                //tmp = t;
                newt = (pptavlnode)t.left;
                t.left.parent = t.parent;
                if (t.parent != null)
                {
                    if (t.data > t.parent.data)
                        t.parent.right = t.left;
                    else
                        t.parent.left = t.left;

                }
                else
                    root = (pptavlnode)t.left; //tricky place, need to fix root as well.

               if (t.left.right!=null)
                    t.left.right.parent = t;

                tmp=(pptavlnode)t.left.right;
                
                t.left.right = t;
                
                t.parent = t.left;

                t.left = tmp;

                pptg.newslide();
                drawtree(margin, pptg.w, pptg.h, margin, noderadius);
              
            }

            return newt;
        
        }


       pptavlnode checkdeletebalancefactor(pptrbnode t)
       {
           int lsth, rsth; // left subtree height, right subtree height
           pptavlnode p = (pptavlnode)t;

           while (p != null)
           {


               if (p.left == null)
                   lsth = 0;
               else
                   lsth = p.left.getheight();

               if (p.right == null)
                   rsth = 0;
               else
                   rsth = p.right.getheight();

               p.balance = lsth - rsth;
               if (Math.Abs(p.balance) == 2) 
                   break;
               // here is tricky 0 means need to continue to check, -1 and 1 may means ok, but doesn't hurt to continue to check.
               // to make the program more efficient, become -1 or 1 or become 0 may be detected by comparing two status before and after
               //which I didn't do it here.
               p = (pptavlnode)p.parent;


           }



           if (p == null) return null; // reached root, no portion skewed to 2 
           if (p.balance == 0) return null; // balanced already.
           //otherwise imbalance has been detected.

           return p;

       }
       pptavlnode checkinsertbalancefactor(pptrbnode t)
       {
           int lsth, rsth; // left subtree height, right subtree height
           pptavlnode p = (pptavlnode)t;

           while (p!=null)
           {
               

               if (p.left == null)
                   lsth = 0;
               else
                   lsth = p.left.getheight();

               if (p.right == null)
                   rsth = 0;
               else
                   rsth = p.right.getheight();

               p.balance = lsth - rsth;
               if (p.balance == 0 || Math.Abs(p.balance) == 2)
                    break;
               p = (pptavlnode)p.parent;
           }

          

           if (p == null) return null; // reached root, no portion skewed to 2 
           if (p.balance == 0) return null; // balanced already.
           //otherwise imbalance has been detected.

           return p;

       }
        */
        /* pptavlnode checkbalancefactor(pptavlnode  t)
         {
             int lsth, rsth; // left subtree height, right subtree height
             pptavlnode p= t;

             do
             {
                 p = (pptavlnode)p.parent;

                 if (p == null) break;

                 if (p.left == null)
                     lsth = 0;
                 else
                     lsth = p.left.getheight();

                 if (p.right == null)
                     rsth = 0;
                 else
                     rsth = p.right.getheight();
                
                 p.balance = lsth - rsth;
             }

             while (p.balance != 0 && Math.Abs(p.balance)!=2);

             if (p == null) return null; // reached root, no portion skewed to 2 
             if (p.balance == 0) return null; // balanced already.
             //otherwise imbalance has been detected.

             return p;
 
         }
         */
        

       

        /*
         public override pptrbnode delete(int pdata)
        {
         
             pptrbnode tmp =(pptrbnode)base.delete(pdata);
            pptg.newslide();
            drawtree(margin, pptg.w, pptg.h, margin, noderadius);
            
             pptrbnode imbalancednode = checkdeletebalancefactor(tmp);
            
             int branch;
           
             while (imbalancednode != null)
            {
                tmp=rotate(imbalancednode);
                imbalancednode = checkdeletebalancefactor(tmp);
             }

            return (pptrbnode )tmp;

          
        }
        */

    }
}
